import java.util.*;

/**
 * 919. 完全二叉树插入器
 * https://leetcode-cn.com/problems/complete-binary-tree-inserter/
 */
public class Solutions_919 {
    public static void main(String[] args) {
        String str = "[1 2 3 4 5 6]";
        TreeNode root = MyTreeNodeUtils.deserialize(str);
        CBTInserter obj = new CBTInserter(root);
        int res1 = obj.insert(7);
        int res2 = obj.insert(8);
        TreeNode res3 = obj.get_root();
        System.out.println("");
    }
}

/**
 * 解法二：队列（28ms）
 */
class CBTInserter {
    TreeNode root;
    // 队列中记录的是没有两个子节点的节点
    Queue<TreeNode> queue;

    public CBTInserter(TreeNode root) {
        queue = new LinkedList<>();
        this.root = root;

        // 将 root 添加到 queue 中
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.peek();
            if (node.left != null) {
                queue.add(node.left);
            } else {
                break;
            }
            if (node.right != null) {
                queue.add(node.right);
            } else {
                break;
            }
            queue.poll();
        }
    }

    public int insert(int v) {
        if (queue.isEmpty()) {
            return -1;
        }
        TreeNode curNode = new TreeNode(v);
        // 当前节点的父节点
        TreeNode parentNode = queue.peek();
        if (parentNode.left == null) {
            // 作为左子节点
            parentNode.left = curNode;
        } else {
            // 作为右子节点
            parentNode.right = curNode;
            // 已经添加右子节点了，说明 parentNode 节点下已经有两个子节点
            queue.poll();
        }
        queue.add(curNode);
        return parentNode.val;
    }

    public TreeNode get_root() {
        return root;
    }
}

/**
 * 解法一：完全二叉树性质（20ms）
 * 计算节点的索引（由子节点的索引计算出父节点的索引）
 */
class CBTInserter2 {
    List<TreeNode> nodes;
    Queue<TreeNode> queue;

    public CBTInserter2(TreeNode root) {
        queue = new LinkedList<>();
        nodes = new ArrayList<>();

        // 将 root 添加到 queue 中
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                nodes.add(node);
            }
        }
    }

    public int insert(int v) {
        TreeNode curNode = new TreeNode(v);
        // 当前添加节点所在的索引（根节点索引为 0）
        int curIdx = nodes.size();
        // 通过子节点索引，定位到父节点所在
        int parentIdx = (curIdx - 1) / 2;
        TreeNode parentNode = nodes.get(parentIdx);
        if (curIdx % 2 == 1) {
            // 左了节点
            parentNode.left = curNode;
        } else {
            // 右子节点
            parentNode.right = curNode;
        }
        // 当前节点添加到列表中
        nodes.add(curNode);
        // 返回父节点值
        return nodes.get(parentIdx).val;
    }

    public TreeNode get_root() {
        return nodes.get(0);
    }
}

